//
// Description: 62. 不同路径
// Created by Loading on 2021/9/25.
//

#include <bits/stdc++.h>

using namespace std;

/* 动态规划，时间复杂度：O(mn) */
int uniquePaths(int m, int n) {
    // dp 数组，dp[i][j] 表示走到 <i, j> 位置时的路径数
    int dp[m][n];
    for (int i = 1; i < n; ++i) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; ++i) {
        dp[i][0] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

/* 数学法，时间复杂度：O(m) */
int uniquePaths_Math(int m, int n) {
    // 需要移动 m + n - 2 次，其中有 m - 1 次向下移动，n - 1 次向右移动
    // 从 m + n - 2 中选择 m - 1 个数的方案数即为答案
    long long res = 1;
    for (int i = n, j = 1; j < m; ++i, ++j) {
        res = res * i / j;
    }
    return (int) res;
}

int main() {
    int m = 3, n = 7;
    int res = uniquePaths(m, n);
    cout << res << endl;

    res = uniquePaths_Math(m, n);
    cout << res << endl;

    return 0;
}